#include"vital_path.h"

using namespace std;

bool topsort(int n, int g[][N], int *ve, int *queue)
{
    int din[N] = {0};
    int dout[N] = {0};

    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (check(i, j, g)) {
                din[j]++;
                dout[i]++;
            }
    int num_of_end_vertex = 0;
    for (int i = 1; i <= n; i++) {
        if (!din[i])queue[++tt] = i;
        if (!dout[i])num_of_end_vertex++;
    }

    if (tt || num_of_end_vertex != 1)return false;

    while (hh <= tt) {
        int t = queue[hh++];
        for (int i = 1; i <= n; i++)
            if (check(t, i, g)) {
                din[i]--;
                if (!din[i])queue[++tt] = i;
                ve[i] = max(ve[t] + g[t][i], ve[i]);
            }
    }
    if (tt == n - 1)return true;
    return false;
}

void get_vl(int n, int g[][N], int *ve, int *vl, int *queue)
{
    for (int i = n - 1; i >= 0; i--) {
        int u = queue[i];
        if (i == n - 1)vl[u] = ve[u];
        else {
            for (int j = 1; j <= n; j++)
                if (check(u, j, g))vl[u] = min(vl[u], vl[j] - g[u][j]);
        }
    }
}

void print_path(int n, int g[][N], char *data,
                int *ve, int *vl, int *queue,
                bool is_vital_path[][N])
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (g[i][j] && ve[i] == vl[j] - g[i][j])is_vital_path[i][j] = true;
        }
    int start = queue[0];
    int end = queue[n - 1];
    int p = start;
    printf("Vital path:%c", data[p]);
    while (p != end)
        for (int i = 1; i <= n; i++) {
            if (is_vital_path[p][i]) {
                p = i;
                printf("->%c", data[p]);
            }
        }
    printf("\nEND");
}

void print_vital_path(int n, int g[][N], char *data,
                      int *ve, int *vl, int *queue,
                      bool is_vital_path[][N]
)
{
    get_vl(n, g, ve, vl, queue);
    print_path(n, g, data, ve, vl, queue, is_vital_path);
}
